<html>
<head><meta charset="utf-8"><title>incremental reparsing in Lark · t-compiler/rust-analyzer · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/index.html">t-compiler/rust-analyzer</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/incremental.20reparsing.20in.20Lark.html">incremental reparsing in Lark</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="158984096"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/incremental%20reparsing%20in%20Lark/near/158984096" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/incremental.20reparsing.20in.20Lark.html#158984096">(Feb 20 2019 at 15:18)</a>:</h4>
<p><span class="user-mention" data-user-id="133169">@matklad</span> one thing I wanted to mention. I think we talked about this briefly at the all hands, but I don't think anybody else may have heard it. One approach to incremental reparsing that I was consdering in Lark, but never implemented, was to really leverage salsa and hence enable incremental re-parsing in quite an automatic way. </p>
<p>In Lark, the base query currently gives back a <code>&amp;[u8]</code> slice of the file. The rough idea was to next do a very quick "repackaging" of that into trees -- basically grouping together <code>{..}</code> tokens. Thus you don't index into the file in an absolute way to identify a token, but rather your index becomes a kind of tree, identifying the path to the <code>{}</code> and the token within.</p>
<p>The actual parser itself would track its position as this kind of tree -- when it comes to a <code>{</code> token, and it needs to compute the "next" index, it would load the set of children of the <code>{</code> token, etc. </p>
<p>This way, when we make a change, we would have to recompute the <em>tree</em>, but that is very cheap-- and after that, we only have to reparse the affected things. Since most edits occur somewhere within a <code>{...}</code>, this implies that the data outside of those <code>{}</code> is not affect (and in particular, the path to it is not affected by how many characters appear within the <code>{}</code>).</p>



<a name="158984154"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/incremental%20reparsing%20in%20Lark/near/158984154" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/incremental.20reparsing.20in.20Lark.html#158984154">(Feb 20 2019 at 15:19)</a>:</h4>
<p>I suspect that whatever tree setup we end up with, we will be able to create salsa-ified incremental variants around it.</p>



<a name="158984512"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/incremental%20reparsing%20in%20Lark/near/158984512" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/incremental.20reparsing.20in.20Lark.html#158984512">(Feb 20 2019 at 15:23)</a>:</h4>
<p>rust-analyzer works in a similar way, but this is implemented manually, not automatically. </p>
<p>When an edit happens, we find the nearest enclosing <code>{}</code>, relex it  and , if  {} are still matched up, reparse only this region, retaining the rest of the syntax tree.</p>



<a name="158984682"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/incremental%20reparsing%20in%20Lark/near/158984682" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/incremental.20reparsing.20in.20Lark.html#158984682">(Feb 20 2019 at 15:25)</a>:</h4>
<p>And a usual note that incremental re parsing is not <strong>too</strong> important. In IntelliJ for Java, while <code>{}</code> are usually automatically paired by the editor, if you type <code>{</code> in <code>if (condition) {</code>, IDE does <strong>not</strong> add closing <code>} </code> automatically. Instead, <code>}</code> is added when you actually type Enter: that gives a somewhat better typing feeling.</p>



<a name="158984763"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/incremental%20reparsing%20in%20Lark/near/158984763" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/incremental.20reparsing.20in.20Lark.html#158984763">(Feb 20 2019 at 15:26)</a>:</h4>
<p>of course that upaired <code>{</code> completely invalidates the parse tree, but the perf loss is negligible, and so smother typing gets higher priority.</p>



<a name="158984794"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/incremental%20reparsing%20in%20Lark/near/158984794" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/incremental.20reparsing.20in.20Lark.html#158984794">(Feb 20 2019 at 15:26)</a>:</h4>
<p>That is, there's specific code to <strong>suppress</strong> insertion of <code>}</code> after if, while, etc.</p>



<a name="158985972"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/incremental%20reparsing%20in%20Lark/near/158985972" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/incremental.20reparsing.20in.20Lark.html#158985972">(Feb 20 2019 at 15:39)</a>:</h4>
<p><a href="/user_uploads/4715/LrVA6SVlomkAWM-S5YrKQq5q/closing_curly-2019-02-20_18.37.42.webm" target="_blank" title="closing_curly-2019-02-20_18.37.42.webm">closing_curly-2019-02-20_18.37.42.webm</a></p>



<a name="158985992"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/incremental%20reparsing%20in%20Lark/near/158985992" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/incremental.20reparsing.20in.20Lark.html#158985992">(Feb 20 2019 at 15:39)</a>:</h4>
<p>Here's a video with the <code>if {</code> behavior</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>